#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int quick_pass(int a[], int i, int j)
{
    int x = a[i];

    while (i < j) {
        while (i < j && a[j] >= x)
            j --;
        a[i] = a[j];

        while (i < j && a[i] <= x)
            i ++;
        a[j] = a[i];
    }
    a[i] = x;

    return i;
}

int get_big5_1(int a[], int i, int j, int big)
{
    int ret;
    
    ret = quick_pass(a, i, j);
    if (j-ret == big-1)
        return a[ret];
    else if (j-ret > big-1) {
        return get_big5_1(a, ret+1, j, big);
    }
    else
        return get_big5_1(a, i, ret-1, big-(j-ret+1));
}

void quick_sort(int a[], int i, int j)
{
    int m;

    if (i < j) {
        m = quick_pass(a, i, j);
        quick_sort(a, i, m-1);
        quick_sort(a, m+1, j);
    }
}

int main(int argc, char *argv[])
{
    int i, a[10];
    
    srandom(time(NULL));
    for (i = 0; i < 10; i++) {
        a[i] = random()%100;
        printf("%d ", a[i]);
    }
    printf("\n");

    quick_sort(a, 0, 9);
    for (i = 0; i < 10; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    printf("big 5 is %d\n", get_big5_1(a, 0, 9, 5));

    return 0;
}
